package com.c2b.algorithm.leetcode.base;

/**
 * <a href='https://leetcode.cn/problems/remove-k-digits/'>移掉 K 位数字(Remove K Digits)</a>
 * <p>给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1 ：
 *      输入：num = "1432219", k = 3
 *      输出："1219"
 *      解释：移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。
 *
 * 示例 2 ：
 *      输入：num = "10200", k = 1
 *      输出："200"
 *      解释：移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
 *
 * 示例 3 ：
 *      输入：num = "10", k = 2
 *      输出："0"
 *      解释：从原数字移除所有的数字，剩余为空就是 0 。
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>1 <= k <= num.length <= 10^5</li>
 *     <li>num 仅由若干位数字（0 - 9）组成</li>
 *     <li>除了 0 本身之外，num 不含任何前导零</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2024/3/21 14:45
 */
public class LC0402RemoveKDigits_M {

    static class Solution {
        public String removeKdigits(String num, int k) {
            char[] numChars = num.toCharArray();
            StringBuilder sb = new StringBuilder();
            for (char currNum : numChars) {
                while (sb.length() != 0 && currNum < sb.charAt(sb.length() - 1) && k > 0) {
                    sb.setLength(sb.length() - 1);
                    --k;
                }
                sb.append(currNum);
            }
            // 如果 k > 0 ，因为整个数字是递增的顺序，所以从末尾移除k位即可
            for (int i = 0; i < k; i++) {
                sb.deleteCharAt(sb.length() - 1);
            }
            // 移除前导的 0
            while (sb.length() > 0 && sb.charAt(0) == '0') {
                sb.deleteCharAt(0);
            }
            return sb.length() != 0 ? sb.toString() : "0";
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        //System.out.println(solution.removeKdigits("1432219", 3));
        //System.out.println(solution.removeKdigits("10200", 1));
        //System.out.println(solution.removeKdigits("10", 2));
        System.out.println(solution.removeKdigits("1234567890", 9));
    }
}
